package com.peng.leetcode.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * IsSubStructure
 *
 * @author: lupeng6
 * @create: 2021/2/5 17:51
 */
public class IsSubStructure {

    public static void main(String[] args) {
        Integer[] A = {3,4,5,1,2}, B = {4,1};
        TreeNode treeA = TreeMain.array2tree(A);
        TreeNode treeB = TreeMain.array2tree(B);
        System.out.println(new IsSubStructure().isSubStructure(treeA, treeB));
    }

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        // 层级遍历寻找 value == B.val
        if (A == null || B == null) {
            return false;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(A);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.val == B.val) {
                // 判断树是否相同
                if (isEquals(node, B)) {
                    return true;
                }
            }
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return false;
    }

    boolean isEquals(TreeNode node1, TreeNode node2) {
        if (node1 == null || node1.val != node2.val) {
            return false;
        }
        if (node2.left != null) {
            if (!isEquals(node1.left, node2.left)) {
                return false;
            }
        }
        if (node2.right != null) {
            if (!isEquals(node1.right, node2.right)) {
                return false;
            }
        }
        return true;
    }


}
